1. Related Applications
This application is a continuation of a co-pending provisional patent application Ser. No. 60/012/614, filed on Mar. 1, 1996 for a Near Optimal Path Apparatus and Method.
2. The Field of the Invention
This invention relates to computer applications for controlling path dependent apparatus and processes such as networks and, more particularly, to novel systems and methods for providing a near optimal path, or a "pretty good" path through a process of such a network, even in the possible absence of a global knowledge of the system.
3. The Background Art
Many apparatus, machines, devices, and processes use a series of steps. Many times these may execute steps toward a destination or objective, while lacking global knowledge. That is, information is not available to assure that the next step executed is the "best" according to some criterion, or even that the next step will ever bring the process to the desired destination or result in an ultimate solution at all.
For example, directing messages or data packets is a serious traffic control question in many computer-controlled systems and environments. Some of these hardware systems may include individual processors using multiprocessing operating systems running parallel threads depending on various data queues. Also included are parallel processors, whether symmetric or non-symmetric, computer networks (networks or nets) such as a local area network (LAN), wide area network (WAN), or a network of networks (internetwork) depending on routers between networks.
Moreover, processes, processors, networks, and the components of each are not static. At a moment in time, a snapshot may be available to identify some portion of the current state of any process or apparatus. The snapshot may be thought of as an instantaneous view or description of the state or loading of a system at an instant of time. The loaded state may be characterized with reference to a ground, unloaded, base, or vacuum state. Typically a ground, base, or vacuum state of a system may be thought of as the configuration and capacity of the system with no loading. Thus, for example, a base or vacuum state may represent the capacities of components in a system having no activity or data messaging of the applications, processes, threads, data structures, lines, or components (or all of the above) in a system.
To obtain a true global view of all knowledge necessary to define the state of a system, the system would need to be static, or in instant communication. That is, messages take time to arrive, conditions change with time, and only a past state of the system can be completely defined. In an operating apparatus or process, a true global view is unavailable. Thus, a path through the apparatus (system) or process is not actually known, let alone an optimal path.
An instant after any snapshot in a dynamic system is recorded, the snapshot may be invalid. A process may have stopped, a data bit, word, or file may have changed or been deleted from a memory location, a router may go down, a processor may have crashed, an application may be hung or otherwise terminated, any hardware may have been taken off line, and the list goes on.
What is needed is an apparatus and method that can still route message traffic in a way that accommodates the changing and ambiguous nature of a dynamic system. Such a system needs to provide a better view than the static, vacuum, or ground state of the system. At the same time, a system needs to provide this view and provide a path without insisting that the path be perfect or the optimal path. A "pretty good path" or a "near optimal path" using the best "available" information in a dynamic system could be faster and more accurate than one using the ground or vacuum state information. At the same time, such a system could be faster than one that attempts to provide the optimal path. What is needed is an apparatus and method for eliminating part of the domain of choices in order to assure improved performance in the remaining portion of the domain.
Similarly, in individual applications, finding a best path through a process comprising parallel threads is often desirable. A user may need to allocate resources, or a processor may need to do so. Hard and fast rules as to operations may provide several unnecessary bottlenecks to a process during actual operation.
Optimization methods often require too much advance knowledge of a system, more than can be known. Moreover, optimal solutions to the efficient operation of a system may require extensive processing time to achieve. Again, in a dynamic system, the state of all the elements is not static anyway, so an optimal system may be impossible to find, especially in a useful time period.
In general, one may often enter a process not knowing all the upcoming options, let alone the ultimate outcome of each. Many decisions are over the horizon. The information to make them will be available later in the process. That is, certain decisions may be unknown to exist, may be made at intermediate destinations, and may rely on data available only at or shortly before presentation of the decision. Partial decisions can be made in anticipation of future information becoming available.
Like a rambling summer vacation through Europe, or the historic Atlantic seaboard of the United States, decisions may be based on where one is in a process, the cost and time required to advance to the next immediate step or location, whether or not a location, or even the path to it, is currently available at all, and the like. One may even find that an open path has become a cul-de-sac that must be backtracked to continue in a process or path.
What is needed is a generalized method to eliminate some choices, paths, etc., especially obvious choices, like options, destinations, paths, threads, or the like that are logjammed or out of service. Thus, simply improving the domain of possible choices may provide some substantial benefit, a near-optimal path.
In one particular example, such as a drawing package (application), finding a best path along a boundary of a visual feature evident to a user in a visual image is often critical. The human eye can detect features which a drawing or painting application needs to be able to recognize by some other method. For speed and utility, dependence on a user is often inefficient, impossible, time consuming, or inaccurate, requiring extensive editing or re-drawing. For example, to cut a portion of a feature out of an image in order to designate an object comprised of that single feature is a very valuable ability. Presently, no satisfactory tool exists in any drawing package to rapidly, even automatically, and accurately complete this process with a reasonable processing time on the processor accomplishing the function and in a reasonable wait time for a user. The need exists for automatic bounding of a feature recognizable by a human viewer, clipping the feature, and saving it as an individual object for multiple re-use. Defining a near-optimal path around the boundary of the feature in the image would need an automatic pathfinding process that is not available. The current software art requires much user involvement or complex processing algorithms, and often both.
In summary, what is needed is a near-optimal path finding method and apparatus applicable to a dynamic system. The near-optimal path finder should decrease the requirements on user involvement. Path finding is needed that can acknowledge the probable lack of utility of certain paths or portions of paths, and systematically delete them from consideration in a search of possible paths through a dynamic system. Such narrowing of options, leaving a suitable working population of "better" choices of intermediate path segments is needed, to ultimately provide a "pretty good" path. Thus, the term "near-optimal," as used here, need not be as rigorously construed as the terms "optimal" or "near-optimal" would be in the mathematical theory of optimization.